package danran.graph;

import java.util.*;

/**
 * @Classname Dijkstra
 * @Description TODO
 * @Date 2021/10/13 12:11
 * @Created by ASUS
 */
public class Dijkstra {
    static class Child {
        public int name;
        public int weight;

        public Child(int name, int weight) {
            this.name = name;
            this.weight = weight;
        }

        public int getWeight() {
            return weight;
        }

        @Override
        public String toString() {
            return "Child{" +
                    "name=" + name +
                    ", weight=" + weight +
                    '}';
        }
    }

    public Map<Integer, List<Child>> createGraph() {
        int[][] graph = new int[][]{
                {0, 1, 2}, {0, 3, 1},
                {1, 3, 3}, {1, 4, 6},
                {2, 0, 4}, {2, 5, 5},
                {3, 2, 2}, {3, 4, 2}, {3, 5, 8}, {3, 6, 4},
                {4, 6, 1},
                {6, 5, 1}
        };
        Map<Integer, List<Child>> g = new HashMap<>();

        for (int[] member : graph) {
            int start = member[0], end = member[1], weight = member[2];
            List<Child> children = g.getOrDefault(start, new ArrayList<>());
            children.add(new Child(end, weight));
            g.put(start, children);
        }
//        g.entrySet().forEach(System.out::println);
        return g;
    }

    public Map<Integer, List<Integer>> getMinPath(Map<Integer, List<Child>> g, int start, int end, int nodeAmount) {
        // initialize
        PriorityQueue<Child> q = new PriorityQueue<>(Comparator.comparing(Child::getWeight));
        int[] distance = new int[nodeAmount];
        Arrays.fill(distance, Integer.MAX_VALUE);
        int[] before = new int[nodeAmount];
        Arrays.fill(before, -1);
        distance[start] = 0;
        q.offer(new Child(start, 0));
        while (!q.isEmpty()) {
            Child cur = q.poll();
            List<Child> children = g.getOrDefault(cur.name, new ArrayList<>());
            for (Child child : children) {
                int name = child.name;
                int weight = child.weight + distance[cur.name];
                if (weight < distance[name]) {
                    distance[name] = weight;
                    before[name] = cur.name;
                    q.offer(new Child(name, distance[name]));
                }
            }
        }
//        System.out.println(Arrays.toString(distance));
//        System.out.println(Arrays.toString(before));
        int dis = 0;
        List<Integer> pathList = new LinkedList<>();
        int cur = end;
        while (cur != -1) {
            pathList.add(0, cur);
            dis += distance[cur];
            cur = before[cur];
        }
        HashMap<Integer, List<Integer>> res = new HashMap<>(1);
        res.put(dis, pathList);
        return res;
    }

    public static void main(String[] args) {
        Dijkstra dijkstra = new Dijkstra();
        Map<Integer, List<Child>> graph = dijkstra.createGraph();
        Map<Integer, List<Integer>> minPath = dijkstra.getMinPath(graph, 2, 6, 7);
        System.out.println(minPath);
    }


    public void pq_test(String[] args) {
        Child child1 = new Child(0, 1);
        Child child2 = new Child(1, 12);
        Child child3 = new Child(2, 4);
        Child child4 = new Child(3, 5);
//        Comparator.comparing(Child::getWeight) ==> 升序
        PriorityQueue<Child> pq = new PriorityQueue<>(Comparator.comparing(Child::getWeight));
        pq.add(child4);
        pq.add(child2);
        pq.add(child1);
        pq.add(child3);
        pq.add(new Child(4, 0));
        System.out.println(pq);
    }
}
